package algorithm.四边形不等式;
/*
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。
如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/super-egg-drop
* */
public class ThrowChessPiecesProblem {

    public static int superEggDrop(int k, int n) {
        int[][] dp = new int[n + 1][k + 1];
        int[][] bestSplit = new int[n + 1][k + 1];
        for (int i = 1; i <= k; i++) {
            dp[1][i] = 1;
            bestSplit[1][i] = 0;
        }

        for (int i = 1; i <= n; i++) {
            dp[i][1] = i;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = k; j > 1; j--) {
                int up = j == k? i - 1: bestSplit[i][j + 1];
                int down = bestSplit[i - 1][j];
                int min = Integer.MAX_VALUE;
                for (int l = up; l >= down; l--) {
                    int tmp = Math.max(dp[l][j - 1], dp[i - 1 - l][j]) + 1;
                    if(tmp < min){
                        min = tmp;
                        bestSplit[i][j] = l;
                    }
                }
                dp[i][j] = min;
            }
        }

        return dp[n][k];

    }


    public static int superEggDrop2(int k, int n) {
        if(n == 1)
            return 1;
        int[] dp = new int[k];
        for (int i = 0; i < k; i++) {
            dp[i] = 1;
        }
        int result = 1;
        while(true){
            int tmp = dp[0];
            dp[0] = ++result;
            if(dp[0] >= n)
                return result;
            for (int i = 1; i < k; i++) {
                int op = dp[i];
                dp[i] = tmp + dp[i] + 1;
                tmp = op;
                if(dp[i] >= n)
                    return result;

            }

        }
    }

    public static void main(String[] args) {
        int i = superEggDrop(3, 40);
        int j = superEggDrop2(3, 40);
        System.out.println(i);
        System.out.println(j);
    }

}
